/*
* Authors: Karymov Anton
*          Skorodumov Kirill
* This file contains headers for branching algorythm.
* June-August,	2011
*/


#include "max_degree_algorythm.h"
#include "types.h"

using namespace boost;

max_degree_algorythm::max_degree_algorythm(graph_t & g_) {
  g = g_;
}

cover_t max_degree_algorythm::get_cover() const { 
  return cover;
}
//Finding a vertex with maximal degree
std::pair<vertex_t,int> max_degree_algorythm::max_degree_vertex()
{
  vertex_t temp_vertex;
  unsigned int delta = 0;
  graph_traits <graph_t>::vertex_iterator i, iend;
  for (tie(i,iend) = vertices(g); i != iend; ++i)
    if (degree(*i, g) > delta)
    {
      delta = degree(*i, g);
      temp_vertex = *i ;
    }
    return std::make_pair(temp_vertex, delta);
}

//checking if graph is covered
bool max_degree_algorythm::is_covered (){
  int edge_num = num_edges(g);

  return edge_num == 0;

}

//finding minimum vertex cover using greedy algorithm
cover_t max_degree_algorythm::greedy_min_vertex_cover(){
  while (!is_covered()){
    vertex_t max_vert = max_degree_vertex().first;
    cover.push_back(max_vert);
    clear_vertex(max_vert, g);
  }
  return cover;
}